package pers.sloera.leetcode.editor.cn;

import cn.hutool.core.io.FileUtil;

import java.nio.charset.StandardCharsets;
import java.util.*;

/**
 * 黑名单中的随机数
 * user sloera
 * date 2022-06-26 12:37:19
 */
class RandomPickWithBlacklist {
    public static void main(String[] args) {
        // Solution solution = new RandomPickWithBlacklist().new Solution(7, new int[]{2, 3, 5});
        String s = FileUtil.readString("./int.txt", StandardCharsets.UTF_8);
        Solution solution = new RandomPickWithBlacklist().new Solution(1000000000, Arrays.stream(s.split(",")).mapToInt(Integer::valueOf).toArray());
        // Solution solution = new RandomPickWithBlacklist().new Solution(2, new int[]{});
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
        System.out.println(solution.pick());
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int restNum;
        // 将黑名单统一映射到后半区
        HashMap<Integer, Integer> blackHashMap;
        Random random = new Random();

        public Solution(int n, int[] blacklist) {
            // [0, n)
            // [0, n - list.length);
            restNum = n - blacklist.length;
            // [n - list.length, n);
            // 注意 blackSet可能会导致内存溢出的问题。所以需要加一个基数 restNum 进行减小空间
            BitSet blackSet = new BitSet();
            blackHashMap = new HashMap<>(blacklist.length);
            Arrays.stream(blacklist).boxed().sorted(Comparator.reverseOrder()).forEach(black -> {
                if (black >= restNum) {
                    blackSet.set(black - restNum);
                } else {
                    int nextClearBit = blackSet.nextClearBit(0);
                    blackSet.set(nextClearBit);
                    blackHashMap.put(black, nextClearBit + restNum);
                }
            });
            // System.out.println(n);
            // System.out.println(blackHashMap.size());
            // System.out.println(count);
        }

        public int pick() {
            // 平均概率
            // [0, n - list.length)
            int nextInt = random.nextInt(restNum);
            return blackHashMap.getOrDefault(nextInt, nextInt);
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}